package leetcode.dp;

/**
 * 2 1 3 4
 * 6
 *
 * @author mazouri
 * @create 2021-09-16 21:27
 */
public class _322_coinChange {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;

        int[][] table = new int[coins.length + 1][max];
        for (int i = 0; i < max; i++) {
            table[0][i] = max;
        }

        for (int i = 1; i < table.length; i++) {
            for (int j = 1; j < max; j++) {
                if (coins[i - 1] > j) table[i][j] = table[i - 1][j];
                else table[i][j] = Math.min(table[i - 1][j], table[i][j - coins[i - 1]] + 1);
            }
        }

        int res = table[coins.length][amount];

        return res == max ? -1 : res;
    }

    public static void main(String[] args) {
        System.out.println(new _322_coinChange().coinChange(new int[]{2, 1, 3, 4}, 6));
    }
}
